Lemma (Rademacher concentration inequality)

Let R1,…,RnR_1,…,R_n be Rademacher random variables (i.e. uniform ±1\pm 1). Then for any vector 𝐚∈ℝn\mathbf{a} \in \mathbb{R}^n,

Pr[∑i=1nRiai≥t‖𝐚‖2]≤e−t2/2\mathrm{Pr}\left[ \sum_{i=1}^n R_i a_i \geq t \lVert \mathbf{a} \rVert_2 \right] \leq e^{-t^2 /2}

This is the Khintchine inequality.

Notes

References

  1. https://www.chrismusco.com/amlds2023/lectures/lec13_annotated.pdf
  2. https://www.chrismusco.com/amlds2023/notes/lecture13.html
  3. https://almostsuremath.com/2020/08/04/the-khintchine-inequality/
  4. https://en.wikipedia.org/wiki/Rademacher_distribution
  5. https://tongzhang-ml.org/lt-book/chap06-rademacher-concentration-slides.pdf
  6. https://cs.stanford.edu/~ermon/papers/rademacher-aaai2018.pdf
  7. https://piazza.com/class_profile/get_resource/khs64r6r5yn154/km1at8uo4o3mk